//给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
//请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

//示例 1：
//输入：nums = [100,4,200,1,3,2]
//输出：4
//解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
//示例 2：
//输入：nums = [0,3,7,2,5,8,4,6,0,1]
//输出：9

//提示：
//0 <= nums.length <= 105
//-109 <= nums[i] <= 109

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;


class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.size() < 2) return nums.size();

        sort(nums.begin(), nums.end());
        int cnt=1;
        int cnt_max = 0;
        int tmp = nums[0];
        for(auto iter1=nums.begin(), iter2=iter1+1; iter2 != nums.end(); ++iter2){
            if (*iter2 == tmp){
                continue;
            }
            else if(*iter2 == ++tmp){
                ++cnt;
                continue;
            }
            else{
                iter1 = iter2;
                tmp = *iter1;
                cnt_max = max(cnt, cnt_max);
                cnt = 1;
                continue;
            }

        }
        return max(cnt, cnt_max);
    }

};

int main() {
    vector<int> input0 = {0,3,7,2,5,8,4,6,0,1};
    vector<int> input1 = {100,4,200,1,3,2};
    vector<int> input2 = {};
    vector<int> input3 = {0,3,7,2,5,8,4,6,0,1};
    vector<int> input4 = {1,2,0,1};
    Solution solution;
    int ans = solution.longestConsecutive(input4);
    cout<<ans<<endl;
    return 0;
}
